package com.linwen.excise.algorithm.贪心;

/**
 * @ClassName _递归_小和问题
 * @Description 小和问题
 * @Author zero
 * @DATE 2024/8/11 12:14 PM
 * @Version 1.0
 * <p>
 * 题目：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
 * 举例：
 * 1 3 4 2 5
 * 小和为：1 + （1 + 3） + 1 + （1 + 3 + 4 + 2） = 16
 * <p>
 * 思路： 1. 暴力法：
 * 2. 递归： 找到数组中左边比当前数小的数，累加起来
 */
public class _递归_小和问题 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 5};
        System.out.println(getSum(arr));
        System.out.println(getSum2(arr));
        for (int i : arr) {
            System.out.print(i + "  ");
        }
    }

    public static int getSum(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    result += arr[i];
                }
            }
        }
        return result;
    }

    public static int getSum2(int[] arr) {
        return getSum2(arr, 0, arr.length - 1);
    }

    public static int getSum2(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int leftSum = getSum2(arr, left, mid);
        int rightSum = getSum2(arr, mid + 1, right);
        int merge = merge(arr, left, mid, right);
        return leftSum + rightSum + merge;
    }

    private static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int p0 = left;
        int p1 = mid + 1;
        int k = 0;
        int result = 0;
        // 两边都没到边界
        while (p0 <= mid && p1 <= right) {
            // 边排序边计算小和，排序是为了快速计算，不用去比较
            result += arr[p0] < arr[p1] ? arr[p0] * (right - p1 + 1) : 0;
            temp[k++] = arr[p0] < arr[p1] ? arr[p0++] : arr[p1++];
        }
        while (p0 <= mid) {
            temp[k++] = arr[p0++];
        }
        while (p1 <= right) {
            temp[k++] = arr[p1++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
        return result;
    }


}
